//#include <io.h>
//#include <fcntl.h> 
#include <stdint.h>
#include <cwchar>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>
#include <bitset>
#include <queue>
#include <map>
#include <tuple>
#include <locale>
#include <codecvt>
#include <regex>

using namespace std;

typedef wchar_t Symbol;
typedef basic_string<Symbol> State;
typedef uint64_t Pos;
typedef enum{L, R} Direction;
typedef tuple<State, Symbol> qX;
typedef tuple<State, Symbol, Direction> pYD;
typedef tuple<qX, pYD> Role;
typedef map<qX, pYD>  Roles;
typedef basic_string<Symbol> SourceCode;
using BLANK_t = Symbol;

class Converter;
class Converter {
public:
    static string to_utf8(wstring s)
    {
        std::wstring_convert<std::codecvt_utf8<Symbol>> converter;
        std::string u8_conv = converter.to_bytes(s);
        return u8_conv;
    }
    static wstring from_utf8(string s)
    {
        std::wstring_convert<std::codecvt_utf8<Symbol>> converter;
        std::wstring wchar_conv = converter.from_bytes(s);
        return wchar_conv;
    }
};

class Program: public Roles
{
    void parse(SourceCode& code) 
    {
        wstringstream ss(code);
        wstring str_line;
        wregex regex_nocomment(L"^([^#]*)#*.*$");
        wregex regex_five(L"^"
                          L"\\s*([^\\s,|]+)\\s*[\\s,|]\\s*"
                              L"'?([^,|])'?\\s*[\\s,|]\\s*"
                              L"([^\\s,|]+)\\s*[\\s,|]\\s*"
                              L"'?([^,|])'?\\s*[\\s,|]\\s*"
                              L"([^\\s,|]+)\\s*[\\s,|]?\\s*"
                          L"$"
                            );
        wsmatch result;
        while(getline(ss, str_line)) {
            regex_match(str_line, result, regex_nocomment);
            str_line = result[1];
            if(regex_match(str_line, result, regex_five)) {
                cout << Converter::to_utf8(result[1]) << ' ';
                cout << '\'' << Converter::to_utf8(result[2]) << '\'' << ' ';
                cout << Converter::to_utf8(result[3]) << ' ';
                cout << '\'' << Converter::to_utf8(result[4]) << '\'' << ' ';
                cout << Converter::to_utf8(result[5]) << endl;
                (*this)[qX(result[1],result[2].str()[0])] = 
                    pYD(result[3],result[4].str()[0], (result[5]==L"L")? Direction::L : Direction::R);
            }
        };
    }
public:
    Program():Roles(){}
    Program(Roles roles):Roles(roles){}

    Program(SourceCode code):Roles()
    {
        parse(code);
    }

};


struct Head {
    Program roles;
    State state;
    Pos pos;
};

struct Tape: public vector<Symbol>
{
    Tape& operator+=(Symbol c)
    {
        this->push_back(c);
        return *this;
    }
    Tape(wstring s)
    {
        this->assign(s.begin(),s.end());
    }

    string to_string() const
    {
        const wstring ws(this->begin(),this->end());
        return Converter::to_utf8(ws);
    }
private:

};

class TuringMachine 
{
    uint64_t cycles;
    Head head;
    Symbol BLANK;

    bool halted()
    {
        qX  _qX(head.state, tape[head.pos]);
        
        if (head.roles.contains(_qX)) {
            pYD& _pYD = head.roles[_qX];
            return head.pos == 0 && (get<2>(_pYD) == Direction::L);
        }
        return true;
    }

    void L() {   head.pos--;    }
    void R() {   
        head.pos++; 
        if(tape.size() == head.pos) {
            tape += BLANK;
        }   
    }

public:
    Tape tape;

    TuringMachine(Program program, State q0, Tape tape0, Symbol blank=L' ',Pos pos0=0)
        : cycles(0), BLANK(blank), tape(tape0) ,head()
    {
        head.state = q0;
        head.pos = pos0;
        head.roles = program;
    }

    TuringMachine(string filename)
        : cycles(0), head(), tape{L""}
    {
        map<string,string> map;
        ifstream ifs(filename);
        regex regex_nocomment("^([^#]*)#*.*$");
        regex regex_keyline("^\\s*([^\\s:]+):\\s*$");
        smatch result;
        string cur_segment_name{""};
        for(string str_line; getline(ifs, str_line);) {
            regex_match(str_line, result, regex_nocomment);
            str_line = result[1];
            if(regex_match(str_line, result, regex_keyline)) {
                cur_segment_name = result[1];
                continue;
            }
            if(cur_segment_name == "TRANSITION") {
                map[cur_segment_name] += str_line + string("\n");
            } else if(cur_segment_name == "INIT_STATE") {
                if(str_line != "")
                    map[cur_segment_name] = str_line;
            } else if(cur_segment_name == "BLANK") {
                if(str_line != "") 
                    map[cur_segment_name] = str_line;
            } else if(cur_segment_name == "TAPE") {
                if(str_line != "") 
                    map[cur_segment_name] += str_line;
            } else {
                map[cur_segment_name] += str_line + string("\n");
            }
        }
        assert(map.contains("TRANSITION"));
        assert(map.contains("INIT_STATE"));
        assert(map.contains("BLANK"));
        assert(map.contains("TAPE"));
        head.roles = Program(Converter::from_utf8(map["TRANSITION"]));
        head.state = Converter::from_utf8(map["INIT_STATE"]);
        BLANK      = Converter::from_utf8(map["BLANK"])[0];
        tape       = Tape{Converter::from_utf8(map["TAPE"])};

    }

    TuringMachine& step() 
    {
        display();
        qX _qX(head.state, tape[head.pos]);
        
        if (head.roles.contains(_qX)) {
            const auto current_pos = head.pos;
            pYD& _pYD = head.roles[_qX];

            Direction& _D = get<2>(_pYD);
            if (_D == Direction::L) {
                if(head.pos == 0) {
                    return *this;
                }
                L();
            } else {
                R();
            }
            tie(head.state, tape[current_pos], ignore) = _pYD;
        }
        cycles++;
        return *this;
    }

    TuringMachine& run(uint64_t steps=0) {
        if(steps==0){
            while(!halted()) {
                step();
            }
        } else {
            for(uint64_t i = 0; i < steps; i++) {
                step();
            }
        }
        return *this;
    }

    void display() const
    {
        cout<<cycles<<':'<<endl;
        {
            size_t i = 0;
            for(auto c: tape) {
                if(i==head.pos) cout<<"|"<< Converter::to_utf8(head.state) <<">";
                cout << Converter::to_utf8(wstring(1, c));
                i++;
            }
            cout<<endl;
        }
    }
};

/* class Reader: protected map<string, wstring> {
public:
    Reader(string filename)
    {

    }
    TuringMachine parse()
    {

    }
}; */

int main(int args, char** argv)
{
#if 0
    TuringMachine a
    {
        Program(
            LR"(
                凡是不能识别为五元组的行都是注释行。
                这行是注释
                this line is a comment
                thie l is a L
                this 'l' is-not 'a' L#之后是注释，#之前不是注释
                #comment 'l' comment 'a' L
                not-comment 'l' not-comment 'a' L#comment
                上面一行是五元组
                空 ' ' 哈 '哈' R
                哈 ' ' 喽 '喽' R
                喽 ' ' 沃 '沃' R
                沃 ' ' 德 '德' R
            )"
        ),
        State{L"空"},
        Tape{L" "}
    };
    a.run().display();
#endif

#if 0
    TuringMachine(
        Program{
            LR"(
                识别0{n}1{n}的图灵机
                q0 '0' | q1 'X' R
                q1 '0' | q1 '0' R
                q2 '0' | q2 '0' L
                q1 '1' | q2 'Y' L
                q2 'X' | q0 'X' R
                q0 'Y' | q3 'Y' R
                q1 'Y' | q1 'Y' R
                q2 'Y' | q2 'Y' L
                q3 'Y' | q3 'Y' R
                q3 ' ' | q4 ' ' R
            )"
        },
        State{L"q0"},
        Tape{L"000111"}
    ).run().display();
#endif

#if 0
    TuringMachine(
        Program{
            LR"(
【管理鸭】梦(6679072)  17:06:34
start state : 0
accept state : 1
reject state : 2
BLANK : 0
other charactors : 1 20 1 3 0 R
0 1 3 0 R
0 2 5 0 R
3 0 4 0 R
3 1 3 1 R
3 2 3 2 R
4 0 7 1 L
5 0 6 0 R
5 1 5 1 R
5 2 5 2 R
6 0 7 2 L
7 0 8 0 L
8 1 8 1 L
8 2 8 2 L
8 0 9 1 R
9 1 10 0 R
9 2 12 0 R
10 0 11 0 R
10 1 10 1 R
10 2 10 2 R
11 0 14 1 L
11 1 11 1 R
11 2 11 2 R
12 0 13 0 R
12 1 12 1 R
12 2 12 2 R
13 0 14 2 L
13 1 13 1 R
13 2 13 2 R
14 0 15 0 L
14 1 14 1 L
14 2 14 2 L
15 0 17 0 R
15 1 16 1 L
15 2 16 2 L
16 0 9 0 R
16 1 16 1 L
16 2 16 2 L
17 0 18 0 R
18 1 19 0 R
18 2 20 0 R
19 0 21 0 R
19 1 19 1 R
19 2 19 2 R
20 0 22 0 R
20 1 20 1 R
20 2 20 2 R
21 0 23 0 R
22 0 24 0 R
23 0 25 1 L
23 1 23 1 R
23 2 23 2 R
24 0 25 2 L
24 1 24 1 R
24 2 24 2 R
25 0 26 0 L
25 1 25 1 L
25 2 25 2 L
26 0 27 0 L
26 1 28 1 L
26 2 28 2 L
27 0 29 0 L
27 1 28 1 L
27 2 28 2 L
28 0 18 0 R
28 1 28 1 L
28 2 28 2 L
29 0 29 0 R
29 1 30 1 R
29 2 30 2 R
30 0 31 0 R
30 1 30 1 R
30 2 30 2 R
31 0 32 1 L
32 0 32 0 L
32 1 33 1 L
32 2 33 2 L
33 0 34 0 R
33 1 33 1 L
33 2 33 2 L
34 1 41 1 R
34 2 35 1 R
35 0 36 0 R
35 1 35 1 R
35 2 35 2 R
36 0 36 0 R
36 1 37 1 R
36 2 37 2 R
37 0 38 1 L
37 1 37 1 R
37 2 37 2 R
38 0 39 0 L
38 1 38 1 L
38 2 38 2 L
39 0 39 0 L
39 1 40 1 L
39 2 40 2 L
40 0 34 0 R
40 1 40 1 L
40 2 40 2 L
41 0 47 0 L
41 1 42 1 L
41 2 42 2 L
42 1 42 2 R
42 2 43 1 R
43 0 44 0 L
43 1 35 1 R
43 2 35 2 R
44 1 35 0 R
45 0 45 0 R
45 1 46 1 R
45 2 46 2 R
46 0 48 0 L
46 1 46 1 R
46 2 46 2 R
47 1 45 0 R
47 2 45 0 R
48 1 49 0 L
48 2 49 0 L
49 1 50 2 R
50 0 51 1 L
50 1 50 1 R
50 2 50 2 R
51 1 51 1 L
51 2 52 2 L
52 0 53 0 R
52 1 50 2 R
52 2 52 2 L
53 0 54 0 R
53 1 53 1 R
53 2 53 1 R
54 0 55 1 R
55 0 56 1 L
56 0 57 0 R
56 1 56 1 L
56 2 56 2 L
57 1 58 2 L
58 0 59 0 L
58 1 58 1 L
58 2 58 2 L
59 0 87 0 R
59 1 60 1 L
59 2 61 2 L
60 1 62 1 R
60 2 59 2 L
61 1 59 1 L
61 2 62 2 R
62 1 63 2 L
62 2 63 1 L
63 1 64 1 L
63 2 64 2 L
64 0 87 0 R
64 1 65 2 R
64 2 65 1 R
65 0 66 0 R
65 1 65 1 R
65 2 65 2 R
66 0 67 0 L
66 1 58 2 L
66 2 66 2 R
67 0 68 0 L
67 1 67 1 L
67 2 67 2 L
68 0 72 0 R
68 1 69 1 L
68 2 70 2 L
69 1 71 1 R
69 2 68 2 L
70 1 68 1 L
70 2 71 2 R
71 1 72 1 R
71 2 72 2 R
72 1 73 2 R
72 2 73 2 R
73 1 74 1 R
73 2 74 1 R
74 0 75 0 R
74 1 74 1 R
74 2 74 2 R
75 0 76 0 L
75 1 77 2 L
75 2 75 2 R
76 0 68 0 L
76 2 76 1 L
77 0 78 0 L
77 1 77 1 L
77 2 77 2 L
78 0 82 0 R
78 1 79 1 L
78 2 80 2 L
79 1 81 1 R
79 2 78 2 L
80 1 78 1 L
80 2 81 2 R
81 1 74 2 R
81 2 74 1 R
82 0 85 0 R
82 1 83 1 R
82 2 84 2 R
83 1 82 1 R
83 2 82 1 R
84 1 82 2 R
84 2 82 2 R
85 0 86 1 L
85 1 85 1 R
85 2 85 1 R
86 0 57 0 R
86 1 86 1 L
86 2 86 2 L
87 0 89 0 L
87 1 88 1 R
87 2 88 2 R
88 1 87 2 R
88 2 87 1 R
89 1 90 0 L
89 2 90 0 L
90 1 91 0 R
90 2 91 0 R
91 0 91 0 R
91 1 92 0 R
91 2 92 0 R
92 0 93 0 L
92 1 92 0 R
92 2 92 0 R
93 0 93 0 L
93 1 94 1 R
93 2 94 2 R
94 0 95 0 R
95 0 96 0 R
96 0 97 2 L
97 0 98 0 L
98 0 100 0 L
98 1 99 1 L
98 2 99 2 L
99 0 98 0 L
99 1 99 1 L
99 2 99 2 L
100 0 123 0 R
100 1 101 1 L
100 2 102 2 L

【管理鸭】梦(6679072)  17:06:43
101 1 103 2 R
101 2 100 2 L
102 1 100 1 L
102 2 104 1 R
103 0 113 0 R
103 1 103 2 R
103 2 103 2 R
104 0 105 0 R
104 1 104 1 R
104 2 104 2 R
105 0 106 0 R
105 1 104 1 R
105 2 104 2 R
106 0 107 0 L
106 1 104 1 R
106 2 104 2 R
107 0 107 0 L
107 1 108 1 L
107 2 108 2 L
108 0 109 0 R
108 1 108 1 L
108 2 108 2 L
109 0 110 2 L
109 1 110 2 R
109 2 109 1 R
110 0 111 0 L
110 1 110 1 L
110 2 110 2 L
111 0 100 0 L
111 1 110 1 L
111 2 110 2 L
112 0 113 0 R
112 1 112 1 R
112 2 112 2 R
113 0 114 0 R
113 1 112 1 R
113 2 112 2 R
114 0 115 0 L
114 1 112 1 R
114 2 112 2 R
115 0 115 0 L
115 1 116 1 L
115 2 116 2 L
116 0 117 0 R
116 1 116 1 L
116 2 116 2 L
117 0 118 2 L
117 1 118 2 R
117 2 117 1 R
118 0 119 0 R
118 1 118 1 R
118 2 118 2 R
119 0 120 2 L
120 0 121 0 L
121 0 122 0 L
121 1 121 1 L
121 2 121 2 L
122 0 100 0 L
122 1 121 1 L
122 2 121 2 L
123 0 124 0 R
123 1 123 0 R
123 2 123 0 R
124 0 125 0 R
125 0 126 0 R
125 1 125 1 R
125 2 125 2 R
126 0 127 0 L
126 1 125 1 R
126 2 125 2 R
127 0 128 0 L
128 0 129 0 L
128 1 128 0 L
128 2 128 0 L
129 0 130 0 L
129 1 129 1 L
129 2 129 2 L
130 0 131 0 R
130 1 129 1 L
130 2 129 2 L
131 0 132 0 R
132 1 134 1 L
132 2 135 2 L
134 0 134 0 L
134 1 136 1 R
134 2 136 1 R
135 0 135 0 L
135 1 136 2 R
135 2 136 2 R
136 0 136 0 R
136 1 137 0 R
136 2 137 0 R
137 0 138 0 R
137 1 145 1 L
137 2 147 2 L
138 0 149 0 L
138 1 139 1 L
138 2 142 2 L
139 0 139 0 L
139 1 140 1 R
139 2 140 2 R
140 0 141 0 R
141 0 136 1 R
142 0 142 0 L
142 1 143 1 R
142 2 143 2 R
143 0 144 0 R
144 0 136 2 R
145 0 145 0 L
145 1 146 1 R
145 2 146 2 R
146 0 136 1 R
147 0 147 0 L
147 1 148 1 R
147 2 148 2 R
148 0 136 2 R
149 0 149 0 L
149 1 1 1 L
149 2 1 2 L
            )"
        },
        State{L"0"},
        Tape{L"112"},
        BLANK_t{L'0'}
    ).run().display();
#endif
    TuringMachine(argv[1]).run().display();
    return 0;
}
